{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Short Encoding of Words"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #trie #array #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字典树 #数组 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumLengthEncoding"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #单词的压缩编码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>单词数组 <code>words</code> 的 <strong>有效编码</strong> 由任意助记字符串 <code>s</code> 和下标数组 <code>indices</code> 组成，且满足：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>words.length == indices.length</code></li>\n",
    "\t<li>助记字符串 <code>s</code> 以 <code>'#'</code> 字符结尾</li>\n",
    "\t<li>对于每个下标 <code>indices[i]</code> ，<code>s</code> 的一个从 <code>indices[i]</code> 开始、到下一个 <code>'#'</code> 字符结束（但不包括 <code>'#'</code>）的 <strong>子字符串</strong> 恰好与 <code>words[i]</code> 相等</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个单词数组 <code>words</code> ，返回成功对 <code>words</code> 进行编码的最小助记字符串 <code>s</code> 的长度 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [\"time\", \"me\", \"bell\"]\n",
    "<strong>输出：</strong>10\n",
    "<strong>解释：</strong>一组有效编码为 s = <code>\"time#bell#\" 和 indices = [0, 2, 5</code>] 。\n",
    "words[0] = \"time\" ，s 开始于 indices[0] = 0 到下一个 '#' 结束的子字符串，如加粗部分所示 \"<strong>time</strong>#bell#\"\n",
    "words[1] = \"me\" ，s 开始于 indices[1] = 2 到下一个 '#' 结束的子字符串，如加粗部分所示 \"ti<strong>me</strong>#bell#\"\n",
    "words[2] = \"bell\" ，s 开始于 indices[2] = 5 到下一个 '#' 结束的子字符串，如加粗部分所示 \"time#<strong>bell</strong>#\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [\"t\"]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>一组有效编码为 s = \"t#\" 和 indices = [0] 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= words.length <= 2000</code></li>\n",
    "\t<li><code>1 <= words[i].length <= 7</code></li>\n",
    "\t<li><code>words[i]</code> 仅由小写字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [short-encoding-of-words](https://leetcode.cn/problems/short-encoding-of-words/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [short-encoding-of-words](https://leetcode.cn/problems/short-encoding-of-words/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"time\",\"me\",\"bell\"]', '[\"t\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\r\n",
    "        goods = set(words)\r\n",
    "        for word in words:\r\n",
    "            for i in range(1, len(word)):\r\n",
    "                goods.discard(word[i:])\r\n",
    "        return sum(len(word) + 1 for word in goods)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words.sort(key=len, reverse=True)\n",
    "        res = 0\n",
    "        for i in range(len(words)):\n",
    "            for j in range(i):\n",
    "                if words[j][-len(words[i]):] == words[i]:\n",
    "                    break\n",
    "            else:\n",
    "                res += len(words[i]) + 1\n",
    "\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        m = len(words)\n",
    "        for i in range(m):\n",
    "            words[i] = words[i][::-1]\n",
    "        words.sort()\n",
    "        count = len(words[-1])+1\n",
    "        for i in range(m-1):\n",
    "            if words[i+1].startswith(words[i]):\n",
    "                continue\n",
    "            else:\n",
    "                count += len(words[i])+1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "\n",
    "        dic = set(words)\n",
    "\n",
    "        for word in words:\n",
    "            for i in range(1, len(word)):\n",
    "                dic.discard(word[i:])\n",
    "        return sum(len(word) + 1 for word in dic)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words = [word[::-1] for word in words]\n",
    "        words.sort(reverse=True)#按单词大小逆序排序，确保前面的单词\"不小于\"后者\n",
    "        ans, curWord = 0, words[0]\n",
    "        for word in words[1:]:\n",
    "            if curWord.startswith(word):#如果前缀相同，说明可压缩\n",
    "                continue\n",
    "            else:\n",
    "                ans += len(curWord)+1#加上当前可压缩区间的单词长度\n",
    "                curWord = word\n",
    "        ans += len(curWord) + 1 #加上最后一个长度\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        new_words = sorted(map(lambda x: x[::-1], words))\n",
    "        length = len(words)\n",
    "        ans = 0\n",
    "        for i, word in enumerate(new_words):\n",
    "            if i + 1 == length or not new_words[i+1].startswith(word):\n",
    "                ans += len(word) + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        good = set(words)\n",
    "        for word in words:\n",
    "            for k in range(1, len(word)):\n",
    "                good.discard(word[k:])\n",
    "\n",
    "        return sum(len(word) + 1 for word in good)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        #如果一个单词是另一个单词的后缀,就不用添加到答案里了\n",
    "        #贪心地考虑\n",
    "        n=len(words)\n",
    "        check=[True]*n\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                a,b=len(words[i]),len(words[j])\n",
    "                if a<=b:\n",
    "                    if words[j][-a:]==words[i]:\n",
    "                        check[j]=True and check[j]\n",
    "                        check[i]=False and check[i]\n",
    "                    else:\n",
    "                        check[i]=True and check[i]\n",
    "                        check[j]=True and check[j]\n",
    "                else:\n",
    "                    if words[i][-b:]==words[j]:\n",
    "                        check[i]=True and check[i]\n",
    "                        check[j]=False and check[j]\n",
    "                    else:\n",
    "                        check[i]=True and check[i]\n",
    "                        check[j]=True and check[j]\n",
    "        return sum(len(words[i])+1 for i in range(n) if check[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        #如果一个单词是另一个单词的后缀,就不用添加到答案里了\n",
    "        #贪心地考虑\n",
    "        n=len(words)\n",
    "        target=set(words)\n",
    "        for word in words:\n",
    "            for k in range(1,len(word)):\n",
    "                target.discard(word[-k:])\n",
    "        return sum([len(v)+1 for v in target])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        #如果一个单词是另一个单词的后缀,就不用添加到答案里了\n",
    "        #贪心地考虑\n",
    "        n=len(words)\n",
    "        target=set(words)\n",
    "        for word in words:\n",
    "            for k in range(1,len(word)):\n",
    "                target.discard(word[-k:])\n",
    "        return sum([len(v)+1 for v in target])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        # n = 10\n",
    "        # print(words)\n",
    "\n",
    "        words = list(set(words))\n",
    "\n",
    "        def is_contain(s_short, s_long):\n",
    "            if len(s_short) < len(s_long):\n",
    "                if s_short == s_long[len(s_long) - len(s_short):len(s_long)] and len(s_long) - len(s_short) != 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            else:\n",
    "                if s_long == s_short[len(s_short) - len(s_long):len(s_short)] and len(s_short) - len(s_long) != 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "\n",
    "\n",
    "        # print(is_contain(\"me\", \"time\"))\n",
    "        # print(is_contain(\"me4\", \"time\"))\n",
    "        # words.sort(key=lambda x: len(x))\n",
    "        # print(words)\n",
    "        word1 = []\n",
    "        for i in range(len(words)):\n",
    "            for j in range(i, len(words)):\n",
    "                if is_contain(words[i], words[j]) == 1:\n",
    "                    if len(words[i]) <= len(words[j]):\n",
    "                        word1.append(words[i])\n",
    "                    else:\n",
    "                        word1.append(words[j])\n",
    "        # print(f\"word1={word1}\")\n",
    "\n",
    "        word_x = []\n",
    "        for str_x in words:\n",
    "            if word1.count(str_x) == 0:\n",
    "                word_x.append(str_x)\n",
    "\n",
    "        # print(f\"word_x={word_x}\")\n",
    "\n",
    "        return len(\"#\".join(word_x)) + 1\n",
    "\n",
    "\n",
    "# s = Solution()\n",
    "# print(s.minimumLengthEncoding([\"time\", \"me\", \"time\", \"bell\"]))\n",
    "# print(s.minimumLengthEncoding([\"time\", \"time\", \"time\", \"time\"]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        s = ''\n",
    "        indices = []\n",
    "        for word in sorted(words, key=lambda x: -len(x)):\n",
    "            if word not in s:\n",
    "                s += word + '#'\n",
    "                indices.append(len(s))\n",
    "            else:\n",
    "                if all(s[i - len(word) - 1:i-1] != word for i in indices):\n",
    "                    s += word + '#'\n",
    "                    indices.append(len(s))\n",
    "        return len(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BCJ:\n",
    "    def __init__(self,words):\n",
    "        self.words = words\n",
    "        self.father = [i for i in range(len(words))]\n",
    "        self.rank = [1]*len(words)\n",
    "        self.max = [len(words[i]) for i in range(len(words))]\n",
    "\n",
    "    def find(self,x):\n",
    "        if x==self.father[x]:\n",
    "            return x\n",
    "        else:\n",
    "            return self.find(self.father[x])\n",
    "\n",
    "    def unset(self,x,y):\n",
    "        fx = self.find(x)\n",
    "        fy = self.find(y)\n",
    "        if fx == fy:\n",
    "            return    \n",
    "        else:\n",
    "            # if self.rank[fx]<self.rank[fy]:\n",
    "            #     self.father[fx] = fy\n",
    "            #     if self.max[fx]>self.max[fy]:\n",
    "            #         self.max[fy] = self.max[fx]\n",
    "            # else:\n",
    "            #     self.father[fy] = fx\n",
    "            #     if self.max[fy]>self.max[fx]:\n",
    "            #         self.max[fx] = self.max[fy]\n",
    "            #     if self.rank[fx] == self.rank[fy]:\n",
    "            #         self.rank[fx]+=1\n",
    "            if len(self.words[fx]) < len(self.words[fy]):\n",
    "                if self.words[fx] != self.words[fy][len(self.words[fy]) - len(self.words[fx]):]:\n",
    "                    return\n",
    "            elif len(self.words[fx]) >= len(self.words[fy]):\n",
    "                if self.words[fy] != self.words[fx][len(self.words[fx]) - len(self.words[fy]):]:\n",
    "                    return\n",
    "            if self.max[fx]<self.max[fy]:\n",
    "                self.father[fx] = fy\n",
    "            else:\n",
    "                self.father[fy] = fx\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        bcj = BCJ(words)\n",
    "        for i in range(len(words)):\n",
    "            for j in range(i+1,len(words)):\n",
    "                if len(words[i])<len(words[j]):\n",
    "                    if words[i] == words[j][len(words[j])-len(words[i]):]:\n",
    "                        bcj.unset(i,j)\n",
    "                else:\n",
    "                    if words[j] == words[i][len(words[i])-len(words[j]):]:\n",
    "                        bcj.unset(i,j)\n",
    "        sset = {}\n",
    "        for i in range(len(words)):\n",
    "            f = bcj.find(i)\n",
    "            if f not in sset.keys():\n",
    "                sset[f] = [i]\n",
    "            else:\n",
    "                sset[f].append(i)\n",
    "        res = 0\n",
    "        for k in sset.keys():\n",
    "            res+=bcj.max[k]+1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        \n",
    "        words.sort(key= len ,reverse=True)\n",
    "        print(words)\n",
    "        s=\"\"\n",
    "        indices = []\n",
    "        for i in range(len(words)):\n",
    "            if words[i]+\"#\"  in s:\n",
    "                indices.append(s.index(words[i]))\n",
    "            else:\n",
    "                indices.append(len(s))\n",
    "                s=s+words[i]+\"#\"\n",
    "        print(\"s=\",s,\"indices=\",indices)\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.lookup = defaultdict(Trie)\n",
    "        self.allin = True\n",
    "\n",
    "    def insert(self, word):\n",
    "        \"\"\"\n",
    "        Inserts a word into the trie.\n",
    "        \"\"\"\n",
    "        tree = self.lookup\n",
    "        for i in range(len(word)-1,-1,-1):\n",
    "            char = word[i]\n",
    "            if char not in tree:\n",
    "                tree[char] = {}\n",
    "                self.allin = False\n",
    "            tree = tree[char]\n",
    "        tree[\"#\"] = \"#\"\n",
    "        if not self.allin:\n",
    "            self.allin = True\n",
    "            return len(word)+1\n",
    "        else:\n",
    "            return 0\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        res = 0\n",
    "        words.sort(key = lambda x: -len(x))\n",
    "        Tree = Trie()\n",
    "        for i in range(len(words)):\n",
    "            res += Tree.insert(words[i])\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words = list(set(words))\n",
    "        Trie = lambda: collections.defaultdict(Trie)\n",
    "        trie = Trie()\n",
    "        nodes = [reduce(dict.__getitem__, word[::-1], trie) for word in words]\n",
    "        return sum(len(word) + 1 for i, word in enumerate(words) if len(nodes[i]) == 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words.sort(key=lambda x:len(x),reverse=True)\n",
    "        f=Counter()\n",
    "        ans=0\n",
    "        for x in words:\n",
    "            if x not in f:\n",
    "                ans+=len(x)+1\n",
    "                for j in range(len(x)):\n",
    "                   f[x[j:]]+=1\n",
    "        return ans                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        # words = set(words)\n",
    "        # Trie = lambda: defaultdict(Trie)\n",
    "        # trie = Trie()\n",
    "        # nodes = [reduce(dict.__getitem__,word[::-1],trie) for word in words]\n",
    "        # return sum(len(word) + 1 for i, word in enumerate(words) if len(nodes[i]) == 0)\n",
    "        words = list(set(words)) #remove duplicates\n",
    "        #Trie is a nested dictionary with nodes created\n",
    "        # when fetched entries are missing\n",
    "        Trie = lambda: collections.defaultdict(Trie)\n",
    "        trie = Trie()\n",
    "\n",
    "        #reduce(..., S, trie) is trie[S[0]][S[1]][S[2]][...][S[S.length - 1]]\n",
    "        nodes = [reduce(dict.__getitem__, word[::-1], trie)\n",
    "                 for word in words]\n",
    "\n",
    "        #Add word to the answer if it's node has no neighbors\n",
    "        return sum(len(word) + 1\n",
    "                   for i, word in enumerate(words)\n",
    "                   if len(nodes[i]) == 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words = set(words)\n",
    "        Trie = lambda: defaultdict(Trie)\n",
    "        trie = Trie()\n",
    "        nodes = [reduce(dict.__getitem__,word[::-1],trie) for word in words]\n",
    "        return sum(len(word) + 1 for i, word in enumerate(words) if len(nodes[i]) == 0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "\n",
    "        # reverse words\n",
    "        words = [(len(w), w) for w in words]\n",
    "        words.sort(reverse = True)\n",
    "\n",
    "        suffix_d = {}\n",
    "        encoding_len = 0\n",
    "        for _, w in words:\n",
    "            if w not in suffix_d:\n",
    "                for i in range(len(w)):\n",
    "                    suffix_d[w[i:]] = w\n",
    "\n",
    "                encoding_len += len(w) + 1\n",
    "\n",
    "        return encoding_len                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        trie={'max':0}\n",
    "        res=0\n",
    "        for word in words:\n",
    "            word=word[::-1]\n",
    "            cur=trie\n",
    "            for i,alpha in enumerate(word):\n",
    "                if not cur.__contains__(alpha):\n",
    "                    cur[alpha]={\"max\":0}\n",
    "                    cur=cur[alpha]\n",
    "                else:\n",
    "                    cur=cur[alpha]\n",
    "                    if cur['max']!=0:\n",
    "                        res-=cur['max']+1\n",
    "                        cur['max']=0\n",
    "            if len(cur)==1:\n",
    "                cur['max']=i+1\n",
    "                res+=cur['max']+1\n",
    "        return res\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words.sort(key=lambda x:len(x), reverse=True)\n",
    "        pre = set()\n",
    "        res = 0\n",
    "        for word in words:\n",
    "            if word not in pre:\n",
    "                res += len(word)+1\n",
    "                for i in range(1, len(word)+1):\n",
    "                    pre.add(word[-i:])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        word_group_list = []\n",
    "        word_group_tag = {}\n",
    "        for index, word in enumerate(words):\n",
    "            word_lenth = len(word)\n",
    "            is_find = False\n",
    "            if word_group_list:\n",
    "                for group_tag, group in enumerate(word_group_list):\n",
    "                    if word_lenth == group['max_lenth'] and word == group['max_word']:\n",
    "                        is_find = True\n",
    "                        word_group_list[group_tag]['word_index'][index] = word\n",
    "                    elif word_lenth > group['max_lenth'] and group['max_word'] == word[-group['max_lenth']:]:\n",
    "                        is_find = True\n",
    "                        word_group_list[group_tag]['max_word'] = word\n",
    "                        word_group_list[group_tag]['max_lenth'] = word_lenth\n",
    "                        word_group_list[group_tag]['word_index'][index] = word\n",
    "                    elif word_lenth < group['max_lenth'] and word == group['max_word'][-word_lenth:]:\n",
    "                        is_find = True\n",
    "                        word_group_list[group_tag]['word_index'][index] = word\n",
    "                    if is_find:\n",
    "                        word_group_tag[index] = group_tag\n",
    "                        break\n",
    "            if not is_find:\n",
    "                word_group_list.append({'max_word': word, 'max_lenth': len(word), 'word_index': {index: word}})\n",
    "                word_group_tag[index] = len(word_group_list) - 1\n",
    "\n",
    "        s = ''\n",
    "        for group_tag, group in enumerate(word_group_list):\n",
    "            s += group['max_word'] + '#'\n",
    "\n",
    "        return len(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        #方法一\n",
    "        #wordsSet = set(words)\n",
    "        #for word in words:\n",
    "        #    for j in range(1,len(word)):\n",
    "        #        wordsSet.discard(word[j:])\n",
    "        \n",
    "        #return sum(len(word)+1 for word in wordsSet)\n",
    "        #方法二：字典树\n",
    "\n",
    "        words = list(set(words)) #remove duplicates\n",
    "        #Trie is a nested dictionary with nodes created\n",
    "        # when fetched entries are missing\n",
    "        Trie = lambda: collections.defaultdict(Trie)\n",
    "        trie = Trie()\n",
    "\n",
    "        #reduce(..., S, trie) is trie[S[0]][S[1]][S[2]][...][S[S.length - 1]]\n",
    "        nodes = [reduce(dict.__getitem__, word[::-1], trie)\n",
    "                 for word in words]\n",
    "\n",
    "        #Add word to the answer if it's node has no neighbors\n",
    "        return sum(len(word) + 1\n",
    "                   for i, word in enumerate(words)\n",
    "                   if len(nodes[i]) == 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class PrefixTree:\n",
    "    def __init__(self):\n",
    "        self.trees = {}\n",
    "\n",
    "    def insert(self, word):\n",
    "\n",
    "        cur_trees = self.trees\n",
    "        idx = 0\n",
    "        for s in word:\n",
    "            if s in cur_trees:\n",
    "                cur_trees[s][\"is_word\"] = False\n",
    "            else:\n",
    "                cur_trees[s] = {\"is_word\": False}\n",
    "            cur_trees = cur_trees[s]\n",
    "            idx += 1\n",
    "        if len(cur_trees) == 1:\n",
    "            cur_trees[\"is_word\"] = True\n",
    "\n",
    "    def search(self, word):\n",
    "        ret = self.search_prefix(word)\n",
    "        if ret:\n",
    "            return ret[\"is_word\"]\n",
    "        return False\n",
    "\n",
    "    def search_prefix(self, prefix):\n",
    "        cur_trees = self.trees\n",
    "        for s in prefix:\n",
    "            if s in cur_trees:\n",
    "                cur_trees = cur_trees[s]\n",
    "            else:\n",
    "                return False\n",
    "        return cur_trees\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.tree = PrefixTree()\n",
    "\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        for word in words:\n",
    "            self.tree.insert(word[-1:-len(word)-1:-1])\n",
    "        ret = []\n",
    "        for word in set(words):\n",
    "            is_word = self.tree.search(word[-1:-len(word)-1:-1])\n",
    "            if is_word:\n",
    "                ret.append(len(word) + 1)\n",
    "        return sum(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words = sorted(words, key= lambda x : len(x), reverse=True)\n",
    "\n",
    "        seen = set()\n",
    "\n",
    "        s = \"\"\n",
    "        for word in words:\n",
    "            if word not in seen:\n",
    "                for i in range(len(word)):\n",
    "                    seen.add(word[i:])\n",
    "                s += word + '#'\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words = sorted(set([x[::-1] for x in words]),key=lambda x:-len(x))\n",
    "        result = 0\n",
    "        root = {}\n",
    "        for word in words:\n",
    "            temp = 0\n",
    "            node = root\n",
    "            for char in word:\n",
    "                if char not in node:\n",
    "                    temp=len(word)+1\n",
    "                node.setdefault(char,{})\n",
    "                node = node[char]\n",
    "            print(temp)\n",
    "            result+=temp\n",
    "        \n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words.sort(key=lambda x:-len(x))\n",
    "        keyset=set()\n",
    "        ans=0\n",
    "        for w in words:\n",
    "            if w in keyset:\n",
    "                continue\n",
    "            ans+=(len(w)+1)\n",
    "            for i in range(len(w)):\n",
    "                if w[i:] not in keyset:\n",
    "                    keyset.add(w[i:])\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        wordtree = [-1] * 27\n",
    "        wordlen = [0] * len(words)\n",
    "        for i, word in enumerate(words):\n",
    "            current = wordtree\n",
    "            flag = False\n",
    "            for char in word[::-1]:\n",
    "                if current[ord(char) - 97] == -1:\n",
    "                    current[ord(char) - 97] = [-1] * 27\n",
    "                    flag = True\n",
    "                    if current[-1] != -1:\n",
    "                        wordlen[current[-1]] = 0\n",
    "                current = current[ord(char) - 97]\n",
    "            if flag:\n",
    "                wordlen[i] = len(word)\n",
    "                current[-1] = i\n",
    "            else:\n",
    "                wordlen[i] = 0\n",
    "\n",
    "        wordnum = 0\n",
    "        for i in wordlen:\n",
    "            if i != 0:\n",
    "                wordnum += 1\n",
    "        return sum(wordlen) + wordnum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node(object):\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.children = []\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words):\n",
    "        self.ans = 0\n",
    "        root_node = Node(\"\")\n",
    "        for word in words:\n",
    "            node = root_node\n",
    "            for i, c in enumerate(word[::-1]):\n",
    "                for child in node.children:\n",
    "                    if child.value == c:\n",
    "                        node = child\n",
    "                        break\n",
    "                else:\n",
    "                    child = Node(c)\n",
    "                    node.children.append(child)\n",
    "                    node = child\n",
    "\n",
    "        self.deep_find(root_node)\n",
    "        return self.ans\n",
    "\n",
    "    def deep_find(self, node, deep=0):\n",
    "        if node.children:\n",
    "            for child in node.children:\n",
    "                self.deep_find(child, deep=deep + 1)\n",
    "        else:\n",
    "            self.ans += deep + 1\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = {}\n",
    "    \n",
    "    def insert(self, word):\n",
    "        tree = self.root\n",
    "        for w in word:\n",
    "            if w not in tree:\n",
    "                tree[w] = {}\n",
    "            tree = tree[w]\n",
    "        tree['#'] = '#'\n",
    "    \n",
    "    def search(self, word):\n",
    "        tree = self.root\n",
    "        for w in word:\n",
    "            if w not in tree:\n",
    "                return False\n",
    "            tree = tree[w]\n",
    "        return '#' in tree\n",
    "\n",
    "    def startwith(self, prefix):\n",
    "        tree = self.root\n",
    "        for p in prefix:\n",
    "            if p not in tree:\n",
    "                return False\n",
    "            tree = tree[p]\n",
    "        return True\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        # 前缀树，单词先按长度从大到小进行排序，单词倒序的前缀相同，直接下一个\n",
    "        trie = Trie()\n",
    "        res = 0\n",
    "        words.sort(key = lambda x:len(x), reverse = True)\n",
    "        for word in words:\n",
    "            if trie.startwith(word[::-1]):\n",
    "                continue\n",
    "            else:\n",
    "                trie.insert(word[::-1])\n",
    "                res += len(word) + 1\n",
    "        return res\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 字典树\n",
    "class dictTree:\n",
    "    def __init__(self):\n",
    "        self.dic = {}\n",
    "\n",
    "    def insert(self, v, i):\n",
    "        v = v[::-1]\n",
    "        cur = self.dic\n",
    "        for ch in v:\n",
    "            if ch not in cur:\n",
    "                cur[ch] = {}\n",
    "            cur = cur[ch]\n",
    "        cur['#'] = (i, v)\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        a = dictTree()\n",
    "        for i, word in enumerate(words):\n",
    "            a.insert(word, i)\n",
    "        cur = a.dic\n",
    "        ret = 0\n",
    "        def dfs(cur):\n",
    "            nonlocal ret\n",
    "            if len(cur) == 1 and '#' in cur:\n",
    "                #print(cur['#'])\n",
    "                ret += len(cur['#'][1]) + 1\n",
    "            else:\n",
    "                for i, v in cur.items():\n",
    "                    if i != '#':\n",
    "                        dfs(v)\n",
    "        dfs(cur)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        trie = {}\n",
    "        for word in words:\n",
    "            it = trie\n",
    "            for c in reversed(word):\n",
    "                it = it.setdefault(c, {})\n",
    "            it['#'] = True\n",
    "\n",
    "        result = 0\n",
    "        nodes = [(trie, 1)]\n",
    "        while nodes:\n",
    "            node, path = nodes.pop()\n",
    "            for v in node:\n",
    "                if v == '#':\n",
    "                    if len(node) == 1:\n",
    "                        result += path\n",
    "                    continue\n",
    "                nodes.append((node[v], path + 1))\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.children = collections.defaultdict(dict) #self.children 头节点  collections.defaultdict(dict)新节点\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        now = self.children\n",
    "        words = list(set(words))\n",
    "        nowList = []\n",
    "        for word in words:\n",
    "            now = self.children\n",
    "            for w in reversed(word):\n",
    "                if w in now:\n",
    "                    now = now[w]\n",
    "                else:\n",
    "                    now[w] = collections.defaultdict(dict)\n",
    "                    now = now[w]\n",
    "            nowList.append(now)\n",
    "        res = 0\n",
    "        for node,word in zip(nowList,words):\n",
    "            if len(node.keys()) == 0: #叶子节点\n",
    "                res += len(word) + 1\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words = list(set(words)) #remove duplicates\n",
    "        #Trie is a nested dictionary with nodes created\n",
    "        # when fetched entries are missing\n",
    "        Trie = lambda: defaultdict(Trie)\n",
    "        trie = Trie()\n",
    "\n",
    "        #reduce(..., S, trie) is trie[S[0]][S[1]][S[2]][...][S[S.length - 1]]\n",
    "        nodes = [reduce(dict.__getitem__, word[::-1], trie)\n",
    "                 for word in words]\n",
    "\n",
    "        #Add word to the answer if it's node has no neighbors\n",
    "        return sum(len(word) + 1\n",
    "                   for i, word in enumerate(words)\n",
    "                   if len(nodes[i]) == 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words = list(set(words))\n",
    "\n",
    "        Trie = lambda: collections.defaultdict(Trie)\n",
    "        trie = Trie()\n",
    "\n",
    "        nodes = [reduce(dict.__getitem__, word[::-1], trie)\n",
    "                    for word in words]\n",
    "        \n",
    "        \n",
    "        return sum(len(word) + 1 for i, word in enumerate(words) if len(nodes[i]) == 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words=list(set(words))\n",
    "        Trie=lambda:collections.defaultdict(Trie)\n",
    "        trie=Trie()\n",
    "        nodes=[reduce(dict.__getitem__,word[::-1],trie) for word in words]\n",
    "        ans=0\n",
    "        # print(nodes)\n",
    "        for w,n in zip(words,nodes):\n",
    "            if len(n)==0:\n",
    "                ans+=len(w)+1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        \"\"\"直接用一个字典来表示节点，一个空字典意味着这是一个叶子节点，否则字典中的每一个元素都是它的一个孩子\"\"\"\n",
    "        words = list(set(words))  # 需要去重，否则在之后计算“叶子高度”的时候会重复计算\n",
    "        nodes = []  # nodes保存着每个word对应的最后一个节点\n",
    "        # Trie本身就是一个递归函数，该函数递归地返回一个defaultdict类型，且它的默认值是该类型本身\n",
    "        Trie = lambda: collections.defaultdict(Trie)\n",
    "        trie = Trie()\n",
    "        for word in words:\n",
    "            now = trie\n",
    "            for w in word[::-1]:\n",
    "                now = now[w]  # 有这个键，就返回它的值，否则返回一个空字典\n",
    "            nodes.append(now)\n",
    "        ans = 0  # 所有叶子结点代表的单词长度加一的和即为答案\n",
    "        for n, w in zip(nodes, words):\n",
    "            if len(n) == 0:  # 一个空字典，意味着这个节点是个叶子\n",
    "                ans += len(w) + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        tree=Trie()\n",
    "        words.sort()\n",
    "        words.sort(key=len)\n",
    "        for word in words:\n",
    "            tree.insert(word[::-1])\n",
    "        ans = 0\n",
    "        pre = None\n",
    "        for word in words:\n",
    "            if pre and word == pre: continue #避免重复\n",
    "            pre = word\n",
    "            if tree.code(word[::-1]):\n",
    "                ans += len(word) + 1\n",
    "        return ans\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = {}\n",
    "        self.end = -1\n",
    "    def insert(self, word):\n",
    "        curNode = self.root\n",
    "        for c in word:\n",
    "            if not c in curNode:\n",
    "                curNode[c] = {}\n",
    "            curNode = curNode[c]\n",
    "        curNode[self.end] = True\n",
    "    def code(self, word):\n",
    "        curNode = self.root\n",
    "        for n in word:\n",
    "            curNode = curNode[n]\n",
    "        return len(curNode) == 1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words = list(set(words)) #remove duplicates\n",
    "        #Trie is a nested dictionary with nodes created\n",
    "        # when fetched entries are missing\n",
    "        Trie = lambda: collections.defaultdict(Trie)\n",
    "        trie = Trie()\n",
    "\n",
    "        #reduce(..., S, trie) is trie[S[0]][S[1]][S[2]][...][S[S.length - 1]]\n",
    "        nodes = [reduce(dict.__getitem__, word[::-1], trie)\n",
    "                 for word in words]\n",
    "\n",
    "        #Add word to the answer if it's node has no neighbors\n",
    "        return sum(len(word) + 1\n",
    "                   for i, word in enumerate(words)\n",
    "                   if len(nodes[i]) == 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.Trie = {}\n",
    "\n",
    "    def insert(self, word):\n",
    "        \"\"\"\n",
    "        Inserts a word into the trie.\n",
    "        :type word: str\n",
    "        :rtype: void\n",
    "        \"\"\"\n",
    "        curr = self.Trie\n",
    "        for w in word:\n",
    "            if w not in curr:\n",
    "                curr[w] = {}\n",
    "            curr = curr[w]\n",
    "        curr['#'] = 1\n",
    "\n",
    "    def isTail(self, word):\n",
    "        \"\"\"\n",
    "        Returns if the word is in the trie.\n",
    "        :type word: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        curr = self.Trie\n",
    "        for w in word:\n",
    "            curr = curr[w]\n",
    "        return len(curr) == 1\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        trie = Trie()\n",
    "        cnt = 0\n",
    "        words = set(words)\n",
    "        for word in words:\n",
    "            trie.insert(word[::-1])\n",
    "        for word in words:\n",
    "            if trie.isTail(word[::-1]):\n",
    "                cnt += len(word) + 1\n",
    "        return cnt\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.children = collections.defaultdict(dict)\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        now = self.children\n",
    "        words = list(set(words))\n",
    "        nowList = []\n",
    "        for word in words:\n",
    "            now = self.children\n",
    "            for w in reversed(word):\n",
    "                if w in now:\n",
    "                    now = now[w]\n",
    "                else:\n",
    "                    now[w] = collections.defaultdict(dict)\n",
    "                    now = now[w]\n",
    "            nowList.append(now)\n",
    "        res = 0\n",
    "        for node,word in zip(nowList,words):\n",
    "            if len(node.keys()) == 0: #叶子节点\n",
    "                res += len(word) + 1\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\r\n",
    "    def __init__(self):\r\n",
    "        self.dic={}\r\n",
    "        self.res = 0\r\n",
    "        self.lv= 0\r\n",
    "        \r\n",
    "    def insert(self,word):\r\n",
    "        tmp=self.dic\r\n",
    "        for w in word[::-1]:\r\n",
    "            if w not in tmp:\r\n",
    "                tmp[w] = {}\r\n",
    "            tmp=tmp[w]\r\n",
    "        tmp['#']=True\r\n",
    "        \r\n",
    "    # def backtracing(self,dic):\r\n",
    "    #     self.lv +=1\r\n",
    "    #     if not dic:\r\n",
    "    #         self.res +=1\r\n",
    "    #         self.lv = 1\r\n",
    "    #         return\r\n",
    "        \r\n",
    "    #     if len(dic) >1:\r\n",
    "            \r\n",
    "    #         for k in dic:\r\n",
    "    #             self.res +=self.lv\r\n",
    "                \r\n",
    "    #             self.backtracing(dic.get(k))\r\n",
    "    #     else:\r\n",
    "    #         for j in dic:\r\n",
    "    #             self.res +=1\r\n",
    "                \r\n",
    "    #             self.backtracing(dic.get(j))\r\n",
    "            \r\n",
    "    # def search(self):\r\n",
    "\r\n",
    "    #     tmp=self.dic\r\n",
    "    #     self.backtracing(tmp)\r\n",
    "    #     return self.res\r\n",
    "\r\n",
    "    def search(self,word):\r\n",
    "        tmp =self.dic\r\n",
    "        for w in word[::-1]:\r\n",
    "            tmp = tmp[w]\r\n",
    "        return len(tmp) ==1\r\n",
    "        \r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    \r\n",
    "    def minimumLengthEncoding(self, words) -> int:\r\n",
    "        tr = Trie()\r\n",
    "        cnt = 0\r\n",
    "        words = set(words)\r\n",
    "        for wd in words:\r\n",
    "            tr.insert(wd)\r\n",
    "        #print(tr.dic)\r\n",
    "        for d in words:\r\n",
    "            if tr.search(d):\r\n",
    "                cnt+=len(d) + 1\r\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words=list(set(words))\n",
    "        Trie=lambda:collections.defaultdict(Trie)\n",
    "        trie=Trie()\n",
    "        nodes=[]\n",
    "        for word in words:\n",
    "            now=trie\n",
    "            for w in word[::-1]:\n",
    "                now=now[w]\n",
    "            nodes.append(now)\n",
    "        ans=0\n",
    "        # print(nodes)\n",
    "        for w,n in zip(words,nodes):\n",
    "            if len(n)==0:\n",
    "                ans+=len(w)+1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.Trie = {}\n",
    "    def insert(self, word):\n",
    "        curr = self.Trie\n",
    "        for w in word:\n",
    "            if w not in curr:\n",
    "                curr[w] = {}\n",
    "            curr = curr[w]\n",
    "        curr['#'] =  1\n",
    "    def isTail(self, word):\n",
    "        curr = self.Trie\n",
    "        for w in word:\n",
    "            curr = curr[w]\n",
    "        return len(curr) == 1\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        trie = Trie()\n",
    "        cnt = 0\n",
    "        words = set(words)\n",
    "        for word in words:\n",
    "            trie.insert(word[::-1])\n",
    "        for word in words:\n",
    "            if trie.isTail(word[::-1]):\n",
    "                cnt += len(word) + 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        def addWord(root, word):\n",
    "            node = root\n",
    "            for i in range(len(word) - 1, -1, -1):\n",
    "                node = node.setdefault(word[i], {})\n",
    "            node['#'] = None\n",
    "\n",
    "        def calLength(root, word):\n",
    "            node = root\n",
    "            for i in range(len(word) - 1, -1, -1):\n",
    "                node = node.get(word[i])\n",
    "            if len(node) == 1:\n",
    "                return len(word) + 1\n",
    "            return 0\n",
    "\n",
    "        root = {}\n",
    "        length = 0\n",
    "        words = list(set(words))\n",
    "        for word in words:\n",
    "            addWord(root, word)\n",
    "        for word in words:\n",
    "            length += calLength(root, word)\n",
    "\n",
    "        return length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.child = collections.defaultdict(dict)\n",
    "    def insert(self, words):\n",
    "        cur = self.child\n",
    "        for word in words:\n",
    "            if word not in cur.keys():\n",
    "                cur[word] = collections.defaultdict(dict)\n",
    "            cur = cur[word]\n",
    "        cur['#'] = '#'\n",
    "    def startsWith(self, words):\n",
    "        cur = self.child\n",
    "        for word in words:\n",
    "            if word not in cur.keys():\n",
    "                return False\n",
    "            cur = cur[word]\n",
    "        return True\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        for i, word in enumerate(words):\n",
    "            words[i] = word[::-1]\n",
    "        words.sort(key = lambda x: -len(x))\n",
    "\n",
    "        T, ans = Trie(), 0\n",
    "        for word in words:\n",
    "            if not T.startsWith(word):\n",
    "                T.insert(word)\n",
    "                ans += len(word) + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        t = Trie() \n",
    "        res = 0 \n",
    "        for w in sorted(words , key = lambda w:-len(w)):\n",
    "            if not t.startsWith(w[::-1]):\n",
    "                t.insert(w[::-1])\n",
    "                res += len(w) + 1 \n",
    "        return res  \n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = defaultdict(int)\n",
    " \n",
    "    def insert(self, word: str) -> None:\n",
    "        node  = self.root\n",
    "        node['path'] += 1 \n",
    "        for ch in word:\n",
    "            node = node.setdefault(ch,defaultdict(int))\n",
    "            node['path'] += 1 \n",
    "        node[\"end\"] += 1 \n",
    " \n",
    "    def search(self, word: str) -> bool:\n",
    "        node = self.root\n",
    "        for ch in word:\n",
    "            if ch not in node:\n",
    "                return False\n",
    "            node = node[ch]\n",
    "        return node[\"end\"] > 0 \n",
    " \n",
    "    def startsWith(self, prefix: str) -> bool:\n",
    "        node = self.root\n",
    "        for ch in prefix:\n",
    "            if ch not in node:\n",
    "                return False\n",
    "            node = node[ch]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words = [list(reversed(r)) for r in set(words)]\n",
    "\n",
    "        trie = {}\n",
    "        for word in words:\n",
    "            cur = trie\n",
    "            for c in word:\n",
    "                if c not in cur:\n",
    "                    cur[c] = {}\n",
    "                cur = cur[c]\n",
    "            cur['*'] = {}\n",
    "        count = 0\n",
    "        \n",
    "        for word in words:\n",
    "            cur = trie\n",
    "            for c in word:\n",
    "                if c not in cur:\n",
    "                    break\n",
    "                cur = cur[c]\n",
    "                if '*' in cur and len(cur) == 1:\n",
    "                    count += len(word) + 1\n",
    "                    break\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.node = collections.defaultdict(dict)\n",
    "\n",
    "    def insert(self, word):\n",
    "        child = self.node\n",
    "        for s in word:\n",
    "            if s not in child.keys():\n",
    "                child[s] = collections.defaultdict(dict)\n",
    "                child = child[s]\n",
    "            else:\n",
    "                child = child[s]\n",
    "        child[\"#\"] = 1\n",
    "\n",
    "    def is_pri(self, word):\n",
    "        child = self.node\n",
    "        for s in word:\n",
    "            child = child[s]\n",
    "        return len(child) == 1 \n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words = [i[::-1] for i in set(words)]\n",
    "        trie = Trie()\n",
    "        for word in words:\n",
    "            trie.insert(word)\n",
    "        num = 0\n",
    "        for word in words:\n",
    "            if trie.is_pri(word):\n",
    "                num += len(word) + 1\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        \"\"\"\n",
    "        后缀相同的可以共享编码 因此可以构造一颗字典树\n",
    "        如果一个单词恰好是另外一个单词的后缀那么就可以省略编码\n",
    "        \"\"\"\n",
    "        words.sort(key=lambda x:len(x),reverse=True) #按长度由高到低 因为短的才能节省编码\n",
    "        rs = 0\n",
    "        tree = [False for _ in range(26)]\n",
    "        for word in words:\n",
    "            is_suffix = True #是否是否个单词的后缀\n",
    "            p = tree\n",
    "            for c in word[::-1]:\n",
    "                idx = ord(c)-97\n",
    "                if not p[idx]: #没有这个记录 新建一棵树\n",
    "                    p[idx] = [False for _ in range(26)]\n",
    "                    is_suffix = False\n",
    "                p = p[idx]\n",
    "            if not is_suffix:#不是后缀就没法节省编码\n",
    "                rs += len(word)+1\n",
    "        return rs\n",
    "                \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # https://leetcode.cn/problems/short-encoding-of-words/solution/dan-ci-de-ya-suo-bian-ma-by-leetcode-solution/\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words = list(set(words)) #remove duplicates\n",
    "        #Trie is a nested dictionary with nodes created\n",
    "        # when fetched entries are missing\n",
    "        Trie2 = lambda: collections.defaultdict(Trie2)\n",
    "        trie = Trie2()\n",
    "\n",
    "        print(Trie2)\n",
    "\n",
    "        #reduce(..., S, trie) is trie[S[0]][S[1]][S[2]][...][S[S.length - 1]]\n",
    "        nodes = [reduce(dict.__getitem__, word[::-1], trie)\n",
    "                 for word in words]\n",
    "\n",
    "        print(list(nodes))\n",
    "\n",
    "        #Add word to the answer if it's node has no neighbors\n",
    "        return sum(len(word) + 1\n",
    "                   for i, word in enumerate(words)\n",
    "                   if len(nodes[i]) == 0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.children = collections.defaultdict()\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        \"\"\"存储后缀\n",
    "\n",
    "        fwords = set(words)\n",
    "        for w in words:\n",
    "            # 枚举出所有后缀\n",
    "            for i in range(len(w) - 1, 0, -1):\n",
    "                fwords.discard(w[i:])\n",
    "        return sum([len(w)+1 for w in fwords])\n",
    "        \"\"\"\n",
    "\n",
    "        \"\"\"字典树\n",
    "        \"\"\"\n",
    "        head = Node()\n",
    "        words = list(set(words))\n",
    "        nodes = []\n",
    "        for w in words:\n",
    "            now = head\n",
    "            for c in w[::-1]:\n",
    "                if c in now.children:\n",
    "                    now = now.children[c]\n",
    "                else:\n",
    "                    now.children[c] = Node()\n",
    "                    now = now.children[c]\n",
    "            nodes.append(now)\n",
    "        res = 0\n",
    "        for w, n in zip(words, nodes):\n",
    "            if len(n.children) == 0:\n",
    "                res += len(w) + 1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class PrefixTree:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "\n",
    "    def insert(self, word: str):\n",
    "        curr = self\n",
    "        for c in word:\n",
    "            if c not in curr.children:\n",
    "                curr.children[c] = PrefixTree()\n",
    "            curr = curr.children[c]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        tree = PrefixTree()\n",
    "        for word in words:\n",
    "            tree.insert(word[::-1])\n",
    "\n",
    "        def dfs(node, depth):\n",
    "            depth += 1\n",
    "            res = 0\n",
    "            for _, child in node.children.items():\n",
    "                res += dfs(child, depth)\n",
    "            return res if res else depth\n",
    "\n",
    "        return dfs(tree, 0)\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    pass\n",
    "    # assert 10 == Solution().minimumLengthEncoding([\"time\", \"me\", \"bell\"])\n",
    "    # assert 2 == Solution().minimumLengthEncoding([\"t\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self): self.kids = {}\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self): self.root = Node()\n",
    "    def insert(self, s: str, k: int, curr: Node) -> None:\n",
    "        if k == -1: return\n",
    "        if s[k] not in curr.kids: curr.kids[s[k]] = Node()\n",
    "        self.insert(s, k - 1, curr.kids[s[k]])\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, curr: Node, k: int) -> int:\n",
    "        if curr == None: return 0\n",
    "        if not curr.kids: return k + 1\n",
    "        return sum(self.solve(next, k + 1) for next in curr.kids.values())\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        trie = Trie()\n",
    "        for word in words: trie.insert(word, len(word) - 1, trie.root)\n",
    "        return self.solve(trie.root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: list[str]) -> int:\n",
    "        class Node:\n",
    "            def __init__(self, l):\n",
    "                self.l = l\n",
    "                self.children = {}\n",
    "\n",
    "        root = Node(0)\n",
    "\n",
    "        def build(t, w):\n",
    "            if not w:\n",
    "                return\n",
    "            if w[-1] not in t.children:\n",
    "                t.children[w[-1]] = Node(t.l + 1)\n",
    "            build(t.children[w[-1]], w[:-1])\n",
    "\n",
    "        for w in words:\n",
    "            build(root, w)\n",
    "\n",
    "        res = [0]\n",
    "\n",
    "        def vis(t):\n",
    "            if len(t.children) == 0:\n",
    "                if t.l > 0:\n",
    "                    res[0] += t.l + 1\n",
    "            for c in t.children.values():\n",
    "                vis(c)\n",
    "\n",
    "        vis(root)\n",
    "        return res[0]\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    words = [\"time\", \"me\", \"bell\"]\n",
    "    obj = Solution()\n",
    "    print(obj.minimumLengthEncoding(words))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.word_count = 0\n",
    "        self.is_whole_word = False\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        root = Node()\n",
    "        for w in words:\n",
    "            node = root\n",
    "            #wr = w[::-1]\n",
    "            for r in w[::-1]:\n",
    "                if r not in node.children:\n",
    "                    node.children[r] = Node()\n",
    "                node = node.children[r]\n",
    "                node.word_count += 1\n",
    "            node.is_whole_word = True\n",
    "            \n",
    "        res = []\n",
    "        def dfs(node, deeplength):\n",
    "            if not node.children:\n",
    "                res.append(deeplength)\n",
    "                return \n",
    "            for r in node.children:\n",
    "                dfs(node.children[r], deeplength+1)\n",
    "        \n",
    "        dfs(root, 0)\n",
    "        return sum(res) + len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.is_end_of_word = False\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        root = TreeNode()\n",
    "\n",
    "        for word in words:\n",
    "            node = root\n",
    "            for char in reversed(word):\n",
    "                if char not in node.children:\n",
    "                    node.children[char] = TreeNode()\n",
    "                node = node.children[char]\n",
    "            node.is_end_of_word = True\n",
    "            \n",
    "\n",
    "        def dfs(node,depth):\n",
    "            if not node.children:\n",
    "                return depth+1\n",
    "            return sum(dfs(child,depth+1) for child in node.children.values())\n",
    "\n",
    "        return dfs(root,0)\n",
    "\n",
    "        \n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        root = Node()\n",
    "        for w in words:\n",
    "            node = root\n",
    "            #wr = w[::-1]\n",
    "            for r in w[::-1]:\n",
    "                if r not in node.children:\n",
    "                    node.children[r] = Node()\n",
    "                node = node.children[r]\n",
    "            \n",
    "        res = []\n",
    "        def dfs(node, deeplength):\n",
    "            if not node.children:\n",
    "                res.append(deeplength)\n",
    "                return \n",
    "            for r in node.children:\n",
    "                dfs(node.children[r], deeplength+1)\n",
    "        \n",
    "        dfs(root, 0)\n",
    "        return sum(res) + len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.nodes = dict()  # 构建字典\n",
    "        self.is_leaf = False #是否是叶子节点/单词最后一个元素\n",
    "\n",
    "    def insert(self, word: str): #插入一个单词字符串\n",
    "            curr = self\n",
    "            for char in word:\n",
    "                if char not in curr.nodes:\n",
    "                    curr.nodes[char] = TrieNode()\n",
    "                curr = curr.nodes[char]\n",
    "                curr.is_leaf=False\n",
    "            curr.is_leaf = True\n",
    "\n",
    "    def search(self, word:str):#搜索一个单词是否在字典树内\n",
    "        curr = self\n",
    "        for char in word:\n",
    "            if char not in curr.nodes:\n",
    "                return False\n",
    "            curr = curr.nodes[char]\n",
    "        if curr.is_leaf:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words = list(set(words))#去除重复单词\n",
    "        words.sort(key= lambda i:len(i))#按照单词长度从小到大排序，包含短单词后缀的长单词能够把短单词结尾的is_leaf置false，从而删除了字典树内的短单词\n",
    "        root = TrieNode()\n",
    "        ans = 0\n",
    "        for word in words:\n",
    "            root.insert(word[::-1])\n",
    "        for word in words:\n",
    "            if root.search(word[::-1]):\n",
    "                ans += len(word)+1\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DicTree:\r\n",
    "    def __init__(self) -> None:\r\n",
    "        self.slots={}\r\n",
    "        self.ending=-1\r\n",
    "    \r\n",
    "    def insert_reverse(self,word:str):\r\n",
    "        cur=self\r\n",
    "        for c in reversed(word):\r\n",
    "            cur=cur.slots.setdefault(c,DicTree())\r\n",
    "            # cur.ending=idx\r\n",
    "            # idx-=1\r\n",
    "        # cur.ending\r\n",
    "    \r\n",
    "    def find(self,word:str):\r\n",
    "        cur=self\r\n",
    "        for c in reversed(word):\r\n",
    "            if c not in cur.slots:\r\n",
    "                return False\r\n",
    "            cur=cur.slots[c]\r\n",
    "        # return cur.ending\r\n",
    "        return True\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\r\n",
    "        tree=DicTree()\r\n",
    "        words.sort(key=len,reverse=True)\r\n",
    "        total=0\r\n",
    "        for word in words:\r\n",
    "            if not tree.find(word):\r\n",
    "                total+=len(word)+1\r\n",
    "            tree.insert_reverse(word)\r\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.is_end_of_word = False\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        root = TrieNode()\n",
    "        nodes = {}  # This dictionary will hold the reference to the node corresponding to the last character of each word.\n",
    "        \n",
    "        for word in set(words):  # Use set to avoid duplicates\n",
    "            current = root\n",
    "            for char in reversed(word):\n",
    "                if char not in current.children:\n",
    "                    current.children[char] = TrieNode()\n",
    "                current = current.children[char]\n",
    "            \n",
    "            nodes[word] = current\n",
    "        \n",
    "        # Calculate the length of the encoding\n",
    "        encoding_length = 0\n",
    "        for word in nodes:\n",
    "            # If the node corresponding to the last character of the word has no children,\n",
    "            # it means this word is not a suffix of any other word.\n",
    "            if len(nodes[word].children) == 0:\n",
    "                encoding_length += len(word) + 1  # +1 for the '#' character\n",
    "        \n",
    "        return encoding_length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        \n",
    "        self.children = defaultdict()\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "    \n",
    "    def insert(self, word):\n",
    "        cur = self.root\n",
    "        self.is_end = True\n",
    "        for c in word:\n",
    "            if c not in cur.children:\n",
    "                cur.children[c] = Node()\n",
    "                self.is_end = False\n",
    "            cur = cur.children[c]\n",
    "        \n",
    "        return 0 if self.is_end else len(word) + 1\n",
    "        \n",
    "        \n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words.sort(key=lambda x: -len(x))\n",
    "        \n",
    "        trie = Trie()\n",
    "\n",
    "        return sum(trie.insert(word[::-1]) for word in words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class NODE:\n",
    "    def __init__(self):\n",
    "        self.np = []\n",
    "        self.nv = []\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        head = NODE()\n",
    "        for words in words:\n",
    "            p = head\n",
    "            for i in range(len(words)-1, -1, -1):\n",
    "                s = False\n",
    "                for j in range(len(p.nv)):\n",
    "                    if words[i] == p.nv[j]:\n",
    "                        p = p.np[j]\n",
    "                        s = True\n",
    "                        break\n",
    "                if s is False:\n",
    "                    p.nv += [words[i]] \n",
    "                    new = NODE()\n",
    "                    p.np += [new]\n",
    "                    p = new\n",
    "        out = 0\n",
    "        st = [head]\n",
    "        deep = [0]\n",
    "        while(len(st)>0):\n",
    "            p = st[0]\n",
    "            d = deep[0]\n",
    "            if len(p.np) > 0: \n",
    "                st += p.np\n",
    "                deep += [d+1]*len(p.np)\n",
    "            else:\n",
    "                out += d+1\n",
    "            st = st[1:]\n",
    "            deep = deep[1:]\n",
    "        return out\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.children =  defaultdict()\n",
    "        self.isend = False\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "    def insert(self, word):\n",
    "        cur_node = self.root\n",
    "        for w in word:\n",
    "            if w not in cur_node.children:\n",
    "                cur_node.children[w] = Node()\n",
    "            cur_node = cur_node.children[w]\n",
    "        cur_node.isend = True\n",
    "    def search(self, word):\n",
    "        cur_node = self.root\n",
    "        for w in word:\n",
    "            if w not in cur_node.children:\n",
    "                return False\n",
    "            cur_node = cur_node.children[w]\n",
    "        return True\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        c = 0\n",
    "        for i in sorted(words, key = lambda x:len(x), reverse = True):\n",
    "            if not self.search(i[::-1]):\n",
    "                c += len(i) + 1\n",
    "                self.insert(i[::-1])\n",
    "            else:\n",
    "                continue\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode():\n",
    "    def __init__(self):\n",
    "        self.children = collections.defaultdict(TrieNode)\n",
    "        self.isword = False\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        res = 0\n",
    "        count = 0\n",
    "        Trie = TrieNode()\n",
    "        cur_node = Trie\n",
    "        for word in sorted(words, key= lambda word: -len(word)):\n",
    "            for ch in word[::-1]:\n",
    "                if ch not in cur_node.children:\n",
    "                    count += 1\n",
    "                cur_node = cur_node.children[ch]\n",
    "            cur_node = Trie\n",
    "            if count != 0:\n",
    "                res += 1 + len(word)\n",
    "            count = 0\n",
    "        return res\n",
    "                \n",
    "\n",
    "\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class node:\n",
    "    def __init__(self):\n",
    "        self.child = defaultdict()\n",
    "        self.isend = False\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.root = node()\n",
    "    def addword(self, word):\n",
    "        cur = self.root\n",
    "        for w in word:\n",
    "            if w not in cur.child:\n",
    "                cur.child[w] = node()\n",
    "            cur = cur.child[w]\n",
    "        cur.isend = True\n",
    "    def searchword(self, word):\n",
    "        cur = self.root\n",
    "        for w in word:\n",
    "            if w not in cur.child:\n",
    "                return False\n",
    "            cur = cur.child[w]\n",
    "        return True\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words = sorted(words, key = lambda x:len(x), reverse = True)\n",
    "        print(\"words:\", words)\n",
    "        res = 0\n",
    "        for i in words:\n",
    "            if not self.searchword(i[::-1]):\n",
    "                self.addword(i[::-1])\n",
    "                res += len(i) + 1\n",
    "                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words = list(set(words))\n",
    "        trie = Node()\n",
    "        nodes = []\n",
    "        for word in words:\n",
    "            now = trie\n",
    "            for w in reversed(word):\n",
    "                if w in now.children:\n",
    "                    now = now.children[w]\n",
    "                else:\n",
    "                    now.children[w] = Node()\n",
    "                    now = now.children[w] \n",
    "            print(len(now.children))\n",
    "            nodes.append(now)\n",
    "            \n",
    "        \n",
    "        ans = 0\n",
    "        for word,node in zip(words,nodes):\n",
    "            # print(len(node.children))\n",
    "            if len(node.children)==0:\n",
    "                ans+=len(word)+1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words.sort(key=lambda x:len(x),reverse=True)\n",
    "        # print(words)\n",
    "        ans = 0\n",
    "        root = Trie()\n",
    "        for s in words:\n",
    "            ans+=root.insert(s)\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.child = [None for _ in range(26)]\n",
    "        \n",
    "\n",
    "    def insert(self,word):\n",
    "        node = self\n",
    "        isNew = False\n",
    "        for i in range(len(word)-1,-1,-1):\n",
    "            if node.child[ord(word[i])-ord('a')]==None:\n",
    "                isNew = True\n",
    "                node.child[ord(word[i])-ord('a')] = Trie()\n",
    "            node = node.child[ord(word[i])-ord('a')]\n",
    "        return len(word)+1 if isNew else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.child=[None]*26\n",
    "        self.isEnd=False\n",
    "        self.char=''\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        root=TrieNode()\n",
    "        for w in words:\n",
    "            cur=root\n",
    "            word=w[::-1]\n",
    "            for j in range(len(word)):\n",
    "                insert=False\n",
    "                next=ord(word[j])-ord('a')\n",
    "                if not cur.child[next]:\n",
    "                    insert=True\n",
    "                    newNode=TrieNode()\n",
    "                    cur.child[next]=newNode\n",
    "                    newNode.char=cur.char+word[j]\n",
    "                cur=cur.child[next]\n",
    "                if cur.isEnd and j<len(word)-1:\n",
    "                    cur.isEnd=False\n",
    "            if insert:\n",
    "                cur.isEnd=True\n",
    "        res=[]\n",
    "        def dfs(root):\n",
    "            nonlocal res\n",
    "            if not root:\n",
    "                return \n",
    "            if root.isEnd:\n",
    "                res.append(root.char[::-1])\n",
    "            for next in root.child:\n",
    "                dfs(next)\n",
    "        dfs(root)\n",
    "        res='#'.join(res)+'#'\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie():\n",
    "    def __init__(self) -> None:\n",
    "        self.children = [None] * 26\n",
    "        self.isEnd = False\n",
    "\n",
    "    def insert(self, word:str) -> None:\n",
    "        node = self\n",
    "        for w in word:\n",
    "            ch = ord(w) - ord('a')\n",
    "            if not node.children[ch]:\n",
    "                node.children[ch] = Trie()\n",
    "            node = node.children[ch]\n",
    "        node.isEnd = True\n",
    "    def load(self, words_list:list) -> None:\n",
    "        for word in words_list:\n",
    "            self.insert(word)\n",
    "    \n",
    "    def get_mini_Encoding(self) -> int:\n",
    "        def BFS(root):\n",
    "            queue = collections.deque()\n",
    "            queue.append((root, 0))\n",
    "            res = 0\n",
    "            while queue:\n",
    "                node, layer = queue.popleft()\n",
    "                # 判断是否为尾巴节点\n",
    "                node_list = [nn for nn in node.children if nn]\n",
    "                if node_list == [] and node.isEnd:\n",
    "                    res += layer + 1  \n",
    "                # 展开节点\n",
    "                for nn in node_list:\n",
    "                    queue.append((nn, layer+1))\n",
    "            return res\n",
    "       \n",
    "        return  BFS(self)\n",
    "        \n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words = [x[::-1] for x in words] \n",
    "        t = Trie()\n",
    "        t.load(words)\n",
    "        return t.get_mini_Encoding()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class PrefixTree:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.is_word = False\n",
    "\n",
    "    def insert(self, word: str):\n",
    "        curr = self\n",
    "        for c in word:\n",
    "            index = ord(c) - ord(\"a\")\n",
    "            if curr.children[index] is None:\n",
    "                curr.children[index] = PrefixTree()\n",
    "            curr = curr.children[index]\n",
    "        curr.is_word = True\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        tree = PrefixTree()\n",
    "        for word in words:\n",
    "            tree.insert(word[::-1])\n",
    "\n",
    "        def dfs(node, depth):\n",
    "            depth += 1\n",
    "            res = 0\n",
    "            for child in node.children:\n",
    "                if child is None:\n",
    "                    continue\n",
    "                res += dfs(child, depth)\n",
    "            return res if res else depth\n",
    "\n",
    "        return dfs(tree, 0)\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    pass\n",
    "    assert 10 == Solution().minimumLengthEncoding([\"time\", \"me\", \"bell\"])\n",
    "    assert 2 == Solution().minimumLengthEncoding([\"t\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "#         words = [word[::-1] for word in words]\n",
    "#         words.sort(reverse=True)         # 按单词大小逆序排序，确保前面的单词“不小于”后者\n",
    "#         ans, curWord = 0, words[0]\n",
    "#         for word in words[1:]:\n",
    "#             if curWord.startswith(word): # 如果前缀相同，说明可压缩\n",
    "#                 continue\n",
    "#             else:\n",
    "#                 ans += len(curWord) + 1  # 加上当前可压缩区间的单词长度\n",
    "#                 curWord = word\n",
    "#         ans += len(curWord) + 1          # 加上最后一个长度    \n",
    "#         return ans\n",
    "\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.child = [None for _ in range(26)]\n",
    "        self.cnt = 0                            # 经过这个节点的单词个数\n",
    "\n",
    "    def insert(self, word: str):\n",
    "        root = self\n",
    "        for c in word[::-1]:\n",
    "            ID = ord(c) - ord(\"a\")\n",
    "            if root.child[ID] == None:\n",
    "                root.child[ID] = Trie()\n",
    "                root.cnt += 1\n",
    "            root = root.child[ID]\n",
    "        root.cnt += 1\n",
    "\n",
    "    def search(self, word:str):\n",
    "        root = self\n",
    "        for c in word[::-1]:\n",
    "            ID = ord(c) - ord(\"a\")\n",
    "            root = root.child[ID]\n",
    "        return root.cnt\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        T = Trie()\n",
    "        words_us = set(words)\n",
    "        for word in words_us:\n",
    "            T.insert(word)\n",
    "        res = 0\n",
    "        for word in words_us:\n",
    "            if T.search(word) == 1:             # 是Trie树里路径最长的那个单词\n",
    "                res += len(word) + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        node = Trie()\n",
    "        words.sort(key=len, reverse=True)\n",
    "\n",
    "        sum = 0\n",
    "        for word in words:\n",
    "            if node.startsWith(word):\n",
    "                continue\n",
    "            node.insert(word)\n",
    "            sum += len(word) + 1\n",
    "        return sum\n",
    "\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.is_end = False\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        trie = self\n",
    "        for ch in reversed(word):\n",
    "            num = ord(ch) - ord(\"a\")\n",
    "            if not trie.children[num]:\n",
    "                trie.children[num] = Trie()\n",
    "            trie = trie.children[num]\n",
    "        trie.is_end = True\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        trie = self\n",
    "        for ch in reversed(word):\n",
    "            num = ord(ch) - ord(\"a\")\n",
    "            if trie.children[num]:\n",
    "                trie = trie.children[num]\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        return trie.is_end\n",
    "\n",
    "    def startsWith(self, prefix: str) -> bool:\n",
    "        trie = self\n",
    "        for ch in reversed(prefix):\n",
    "            num = ord(ch) - ord(\"a\")\n",
    "            if trie.children[num]:\n",
    "                trie = trie.children[num]\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.isWord = False\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        node = self\n",
    "        for s in word:\n",
    "            s_ord = ord(s) - ord('a')\n",
    "            if not node.children[s_ord]:\n",
    "                node.children[s_ord] = Trie()\n",
    "            node = node.children[s_ord]\n",
    "        node.isWord = True\n",
    "        return node\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        node = self\n",
    "        for s in word:\n",
    "            s_ord = ord(s) - ord('a')\n",
    "            if not node.children[s_ord]:\n",
    "                return False\n",
    "            node = node.children[s_ord]\n",
    "        if not node.isWord:\n",
    "            return False\n",
    "        return True\n",
    "\n",
    "    def startsWith(self, prefix: str) -> bool:\n",
    "        node = self\n",
    "        for s in prefix:\n",
    "            s_ord = ord(s) - ord('a')\n",
    "            if not node.children[s_ord]:\n",
    "                return False\n",
    "            node = node.children[s_ord]\n",
    "        return True\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        trie = Trie()\n",
    "        length = 0\n",
    "        words_sorted = list(sorted(words, key=lambda x: len(x), reverse=True))\n",
    "        for word in words_sorted:\n",
    "            rword = word[::-1]\n",
    "            if not trie.startsWith(rword):\n",
    "                trie.insert(rword)\n",
    "                length = length + len(rword) + 1\n",
    "        return length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class PrefixTree:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "\n",
    "    def insert(self, word: str):\n",
    "        curr = self\n",
    "        for c in word:\n",
    "            index = ord(c) - ord(\"a\")\n",
    "            if curr.children[index] is None:\n",
    "                curr.children[index] = PrefixTree()\n",
    "            curr = curr.children[index]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        tree = PrefixTree()\n",
    "        for word in words:\n",
    "            tree.insert(word[::-1])\n",
    "\n",
    "        def dfs(node, depth):\n",
    "            depth += 1\n",
    "            res = 0\n",
    "            for child in node.children:\n",
    "                if child is None:\n",
    "                    continue\n",
    "                res += dfs(child, depth)\n",
    "            return res if res else depth\n",
    "\n",
    "        return dfs(tree, 0)\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    pass\n",
    "    # assert 10 == Solution().minimumLengthEncoding([\"time\", \"me\", \"bell\"])\n",
    "    # assert 2 == Solution().minimumLengthEncoding([\"t\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, x=''):\n",
    "        self.val = x\n",
    "        self.next = {}\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        root = Node()\n",
    "        cur = root\n",
    "        words = [word[::-1] for word in words]\n",
    "\n",
    "        def insert(word):\n",
    "            cur = root\n",
    "            for i in word:\n",
    "                if i not in cur.next:\n",
    "                    cur.next[i] = Node(i)\n",
    "                cur = cur.next[i]\n",
    "\n",
    "        for word in words:\n",
    "            insert(word)\n",
    "\n",
    "        paths = []\n",
    "        def dfs(root, path):\n",
    "            if not root.next:\n",
    "                paths.append(path)\n",
    "            for nxt in root.next:\n",
    "                dfs(root.next[nxt], path + root.next[nxt].val)\n",
    "        dfs(root, \"\")\n",
    "        return sum(len(path)+1 for path in paths)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 820. 单词的压缩编码\n",
    "# 单词数组 words 的 有效编码 由任意助记字符串 s 和下标数组 indices 组成，且满足：\n",
    "# words.length == indices.length\n",
    "# 助记字符串 s 以 '#' 字符结尾\n",
    "# 对于每个下标 indices[i] ，s 的一个从 indices[i] 开始、到下一个 '#' 字符结束（但不包括 '#'）的 子字符串 恰好与 words[i] 相等\n",
    "# 给你一个单词数组 words ，返回成功对 words 进行编码的最小助记字符串 s 的长度 。\n",
    "#\n",
    "# 示例 1：\n",
    "# 输入：words = [\"time\", \"me\", \"bell\"]\n",
    "# 输出：10\n",
    "# 解释：一组有效编码为 s = \"time#bell#\" 和 indices = [0, 2, 5] 。\n",
    "# words[0] = \"time\" ，s 开始于 indices[0] = 0 到下一个 '#' 结束的子字符串，如加粗部分所示 \"time#bell#\"\n",
    "# words[1] = \"me\" ，s 开始于 indices[1] = 2 到下一个 '#' 结束的子字符串，如加粗部分所示 \"time#bell#\"\n",
    "# words[2] = \"bell\" ，s 开始于 indices[2] = 5 到下一个 '#' 结束的子字符串，如加粗部分所示 \"time#bell#\"\n",
    "#\n",
    "# 示例 2：\n",
    "# 输入：words = [\"t\"]\n",
    "# 输出：2\n",
    "# 解释：一组有效编码为 s = \"t#\" 和 indices = [0] 。\n",
    "#\n",
    "# 提示：\n",
    "# 1 <= words.length <= 2000\n",
    "# 1 <= words[i].length <= 7\n",
    "# words[i] 仅由小写字母组成\n",
    "#\n",
    "# 思路A： 把所有字符串反向；排序；去除掉被包含的字符串(从左到右都尝试吃掉前面的字符串): 统计字符串长度和+字符数量即可；\n",
    "# 思路B： 把所有字符串反向；构造字典树；统计叶子数量+叶子节点到root节点的距离\n",
    "\n",
    "# class Solution:\n",
    "#     def minimumLengthEncoding(self, words) -> int:\n",
    "#         # A solution\n",
    "#         new_word = []\n",
    "#         for word in words:\n",
    "#             new_word.append(word[::-1])\n",
    "#         new_word.sort()\n",
    "#         n = len(new_word)\n",
    "#         res = 0\n",
    "#         for i in range(1, n):\n",
    "#             if not new_word[i].startswith(new_word[i - 1]):\n",
    "#                 res += len(new_word[i - 1]) + 1\n",
    "#         res += len(new_word[-1]) + 1\n",
    "#         return res\n",
    "\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    def __init__(self, deep):\n",
    "        self.children = [None] * 26\n",
    "        self.isEnd = True\n",
    "        self.deep = deep\n",
    "\n",
    "    def insert(self, word: str):\n",
    "        pos = ord(word[0]) - ord('a')\n",
    "        if self.children[pos] is None:\n",
    "            self.children[pos] = Trie(self.deep + 1)\n",
    "            self.isEnd = False\n",
    "        if len(word) > 1:\n",
    "            self.children[pos].insert(word[1:])\n",
    "\n",
    "    def get(self):  # 不是后缀的每个词的长度+1的数组\n",
    "        if self.isEnd:\n",
    "            return self.deep\n",
    "        else:\n",
    "            res = 0\n",
    "            for i in self.children:\n",
    "                if i is not None:\n",
    "                    res += i.get()\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words) -> int:\n",
    "        # B solution\n",
    "        trie = Trie(1)\n",
    "        for word in words:\n",
    "            trie.insert(word[::-1])\n",
    "        return trie.get()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.children=[None]*26\n",
    "        self.isEnd=False\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        node = self\n",
    "        for s in word:\n",
    "            n=ord(s)-ord('a')\n",
    "            if not node.children[n]:\n",
    "                node.children[n]=Trie()\n",
    "            node=node.children[n]\n",
    "        node.isEnd=True\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        node = self\n",
    "        for s in word:\n",
    "            n = ord(s)-ord('a')\n",
    "            if node.children[n]:\n",
    "                node=node.children[n]\n",
    "            else:\n",
    "                return False\n",
    "        return node.isEnd\n",
    "\n",
    "    def startsWith(self, prefix: str) -> bool:\n",
    "        node = self\n",
    "        for s in prefix:\n",
    "            n = ord(s)-ord('a')\n",
    "            if node.children[n]:\n",
    "                node=node.children[n]\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words.sort(key=len,reverse=True)\n",
    "        res=0\n",
    "        cnt=0\n",
    "        t=Trie()\n",
    "        for word in words:\n",
    "            if t.startsWith(word[::-1]):\n",
    "                continue\n",
    "            t.insert(word[::-1])\n",
    "            cnt+=1\n",
    "            res+=len(word)\n",
    "        return res+cnt\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        class Trie:\n",
    "            def __init__(self):\n",
    "                self.cld = {}\n",
    "        Node = Trie()\n",
    "        words = list(set(words))\n",
    "        for word in words:\n",
    "            word = reversed(word)\n",
    "            now = Node\n",
    "            for i in word:\n",
    "                if i in now.cld:\n",
    "                    now = now.cld[i]\n",
    "                else:\n",
    "                    now.cld[i] = Trie()\n",
    "                    now = now.cld[i]\n",
    "        def dfs(node,t):\n",
    "            if len(node.cld)==0:\n",
    "                return t+1\n",
    "            return sum(dfs(node.cld[c],t+1) for c in node.cld)\n",
    "        return dfs(Node,0)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
